package leetcode_1801_1900;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.TreeSet;

public class LeeCode_1878 {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(getBiggestThree(new int[][]{
                {3, 4, 5, 1, 3},
                {3, 3, 4, 2, 3},
                {20, 30, 200, 40, 10},
                {1, 5, 5, 4, 1},
                {4, 3, 2, 2, 5}})));
    }
    private static int[] getBiggestThree(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        TreeSet<Integer> set = new TreeSet<>((o1, o2) -> o2 - o1);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 2 && j == 3)
                    System.out.println();
                set.add(grid[i][j]);
                int t = 1;
                while (i - t >= 0 && i + t < m && j - t >= 0 && j + t < n){
                    int sum = 0;
                    int si = i - t, sj = j, ei = i, ej = j + t;
                    si++;
                    sj++;
                    while (si <= ei && sj <= ej){
                        sum += grid[si][sj];
                        si++;
                        sj++;
                    }
                    si = i;
                    sj = j + t;
                    ei = i + t;
                    ej = j;
                    si++;
                    sj--;
                    while (si <= ei && sj >= ej){
                        sum += grid[si][sj];
                        si++;
                        sj--;
                    }
                    si = i + t;
                    sj = j;
                    ei = i;
                    ej = j - t;
                    si--;
                    sj--;
                    while (si >= ei && sj >= ej){
                        sum += grid[si][sj];
                        si--;
                        sj--;
                    }
                    si = i;
                    sj = j - t;
                    ei = i - t;
                    ej = j;
                    si--;
                    sj++;
                    while (si >= ei && sj <= ej){
                        sum += grid[si][sj];
                        si--;
                        sj++;
                    }
                    set.add(sum);
                    System.out.println(i + " " + j + " " + sum);
                    t++;
                }
            }
        }
        if (set.size() >= 3){
            int[] ans = new int[3];
            for (int i = 0; i < 3; i++) {
                ans[i] = set.pollFirst();
            }
            return ans;
        }else {
            int[] ans = new int[set.size()];
            for (int i = 0; i < ans.length; i++) {
                ans[i] = set.pollFirst();
            }
            return ans;
        }
    }
}
